home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12204 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.1 KB
  1. Path: garden.csc.calpoly.edu!not-for-mail
  2. From: dstubbs@garden.csc.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: level order binary search
  5. Date: 29 Mar 1996 08:57:18 -0800
  6. Organization: Cal Poly, San Luis Obispo
  7. Message-ID: <4jh4pe$ef4@garden.csc.calpoly.edu>
  8. References: <4jf9cd$p4d@aphex.direct.ca>
  9. NNTP-Posting-User: dstubbs@garden.csc.calpoly.edu
  10.  
  11. In article <4jf9cd$p4d@aphex.direct.ca>,
  12. Ed Toivanen <etoivane@direct.ca> wrote:
  13. >What is the algorithm for a level order search of a binary tree?
  14. >Knuth leaves it as an "exercise for the reader".  Peachy.
  15. >
  16. >
  17. >Thanks, Ed
  18. >
  19.  
  20. A level order traverse (or search) looks at the root, then all
  21. nodes at level 2, then all nodes at level 3, and so on. In general
  22. a node at level k is processed after all nodes at level k-1 and
  23. before all nodes at level k+1.
  24.  
  25. The algorithm to do this is the following:
  26.  
  27.    Put the root node in a queue.
  28.    while the queue is not empty
  29.       remove a node from the queue and process it.
  30.       put the children of the node just processed in the queue.
  31.    end while
  32.  
  33. This is similar to the usual pre, in, and post order traversals
  34. except that a queue is used instead of a stack.
  35.  
  36.  
  37.